A triangulated irregular network (TIN) may be represented by data stored in a data structure. A TIN may be used to describe, for example, a three-dimensional surface as a set of irregularly shaped triangles. For example, a surface may be represented as a set of contiguous, non-overlapping triangles. Thus, a TIN may be used in a geographic information system to, for example, facilitate region approximation. A TIN may be used in connection with terrain modeling where terrain characteristics are determined from sets of irregularly distributed points. Within a triangle, a surface is represented by a plane. A triangle may be formed from a set of points known as mass points.
In one example, points used to form the irregular triangles may have x, y, and z coordinates associated with a three-dimensional data point in space on the surface. A terrain may be created by connecting triangles formed from three points represented by (x, y, z) coordinates. Therefore, a TIN may store information that describes the set of irregular triangles. This information may be stored, for example, triangle-by-triangle, point-by-point with neighbor information, and so on.
Delaunay triangulation is one method for performing triangulation. Delaunay triangulation is a proximal method that satisfies the requirement that a circle drawn through the three nodes of a triangle will contain no other node. Triangles formed using Delaunay triangulation have certain advantages. For example, triangles formed using Delaunay triangulation tend to be relatively equiangular. Additionally, Delaunay triangulation tends to be performable independent of the order in which points are processed and tends to ensure that any point on the surface is as close as possible to a node.
Conventionally, it has been difficult, if possible at all, to do in-memory triangulation of arbitrarily large data sets due, for example, to finite memory resources. Some conventional solutions have attempted to remedy this situation by gridding a data set and doing piece-wise in-memory processing. However, excessive boundary conditions associated with gridding have limited the effectiveness of these conventional solutions. Furthermore, these in-memory solutions have not scaled well to arbitrarily large sets of data points.